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, Los Angeles, CA, USA , 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
ID Code:1492

Repository Staff Only: item control page

References

Asplund, E., Grünbaum, B.: On a coloring problem. Mathematica Scandinavica 8, 181–188 (1960)

Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays in Geometric Graph Theory, pp. 213–248. Springer, New York (2012)

de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Comb. Probab. Comput. 3, 233–246 (1994)

Fusy, E.: Transversal structures on triangulations: a combinatorial study and straight-line drawings. Discrete Math. 309(7), 1870–1894 (2009)

Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4(4), 310–323 (1983)

Kang, R.J., Müller, T.: Arrangements of pseudocircles and circles. Discrete Comput. Geom. 51, 896–925 (2014)

Kant, G., He, X.: Regular edge labeling of 44-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172(1–2), 175–193 (1997)

Klawitter, J., Nöllenburg, M., Ueckerdt, T.: Combinatorial properties of triangle-free rectangle arrangements and the squarability problem. CoRR, arXiv:​1509.​00835, September 2015

Koźmiński, K., Kinnen, E.: Rectangular duals of planar graphs. Networks 15, 145–157 (1985)

Schnyder, W.: Planar graphs and poset dimension. Order 5(4), 323–343 (1989)

Schnyder, W.: Embedding planar graphs on the grid. In: 1st ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 138–148 (1990)

Thomassen, C.: Interval representations of planar graphs. J. Comb. Theor. Ser. B 40(1), 9–20 (1986)

Ungar, P.: On diagrams representing graphs. J. London Math. Soc. 28, 336–342 (1953)

Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebraic Discrete Methods 3(3), 351–358 (1982)