Aspect Ratio Universal Rectangular Layouts

DOI10.1007/978-3-030-96731-4_7arXiv2112.03242MaRDI QIDQ6384955

Andrew Nathenson, Stefan Felsner, Csaba D. Tóth

Publication date: 6 December 2021

Abstract: A emph{generic rectangular layout} (for short, emph{layout}) 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. A layout is weakly (strongly) emph{aspect ratio universal} if any assignment of aspect ratios to rectangles can be realized by a weakly (strongly) equivalent layout. We give a combinatorial characterization for weakly and strongly aspect ratio universal layouts, respectively. Furthermore, we describe a quadratic-time algorithm that decides whether a given graph $G$ is the dual graph of a strongly aspect ratio universal layout, and finds such a layout if one exists.

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Aspect Ratio Universal Rectangular Layouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6384955)