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

Klawitter, Jonathan and Nöllenburg, Martin and Ueckerdt, Torsten (2015) Combinatorial Properties of Triangle-Free Rectangle Arrangements and the Squarability Problem. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 231-244(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_20).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Classifications: Z Theory > Z.250 Geometry
Z Theory > Z.500 Representations
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:10
Last Modified: 04 May 2016 16:10
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1492

Actions (login required)

View Item View Item