TY - JOUR
AU - Felsner, Stefan
AU - Nathenson, Andrew
AU - Toth, Csaba D.
PY - 2024/05/17
Y2 - 2024/07/25
TI - Aspect Ratio Universal Rectangular Layouts
JF - Computing in Geometry and Topology
JA - CompGeomTop
VL - 3
IS - 1
SE - Original Research Articles
DO - 10.57717/cgt.v3i1.37
UR - https://cgt-journal.org/index.php/cgt/article/view/37
SP - 3:1-3:24
AB - <p>A <em>generic rectangular layout</em> (for short, <em>layout</em>) is a subdivision of an axis-aligned rectangle into axis-aligned rectangles, no four of which have a point in common. Such layouts are used in data visualization and in cartography. The contacts between the rectangles represent semantic or geographic relations. <br />A layout is weakly (strongly) <em>aspect ratio universal</em> if any assignment of aspect ratios to rectangles can be realized by a weakly (strongly) equivalent layout. We give combinatorial characterizations for weakly and strongly aspect ratio universal layouts. Furthermore, we describe a quadratic-time algorithm that decides whether a given graph is the dual graph of a strongly aspect ratio universal layout, and finds such a layout if one exists.</p>
ER -