M. Nöllenburg, J. Klawitter, T. Ueckerdt:

"Combinatorial Properties of Triangle-Free Rectangle Arrangements and the Squarability Problem";

Talk: Graph Drawing and Network Visualization (GDŽ15), Los Angeles, USA; 2015-09-24 - 2015-09-26; in: "Graph Drawing and Network Visualization (GD'15)", E. Di Giacomo, A. Lubiw (ed.); Springer, LNCS 9411 (2015), ISBN: 978-3-319-27260-3; 231 - 244.

We consider arrangements of axis-aligned rectangles in the plane. A geometric arrangement specifies the coordinates of all rectangles, while a combinatorial arrangement specifies only the respective intersection type in which each pair of rectangles intersects. First, we investigate combinatorial contact arrangements, i.e., arrangements of interior-disjoint rectangles, with a triangle-free intersection graph. We show that such rectangle arrangements are in bijection with the 4-orientations of an underlying planar multigraph and prove that there is a corresponding geometric rectangle contact arrangement. Using this, we give a new proof that every triangle-free planar graph is the contact graph of such an arrangement. Secondly, we introduce the question whether a given rectangle arrangement has a combinatorially equivalent square arrangement. In addition to some necessary conditions and counterexamples, we show that rectangle arrangements pierced by a horizontal line are squarable under certain sufficient conditions.

Created from the Publication Database of the Vienna University of Technology.