On Balanced -Contact Representations

Durocher, Stephane and Mondal, Debajyoti (2013) On Balanced -Contact Representations. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 143-154(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_13).

Full text not available from this repository.


In a -contact representation of a planar graph G, each vertex is represented as an axis-aligned plus shape consisting of two intersecting line segments (or equivalently, four axis-aligned line segments that share a common endpoint), and two plus shapes touch if and only if their corresponding vertices are adjacent in G. Let the four line segments of a plus shape be its arms. In a c-balanced representation, c ≤ 1, every arm can touch at most ⌈cΔ⌉ other arms, where Δ is the maximum degree of G. The widely studied T- and L-contact representations are c-balanced representations, where c could be as large as 1. In contrast, the goal in a c-balanced representation is to minimize c. Let c k , where k ∈ {2,3}, be the smallest c such that every planar k-tree has a c-balanced representation. In this paper we show that 1/4 ≤ c 2 ≤ 1/3 ( = b 2) and 1/3 < c 3 ≤ 1/2 ( = b 3). Our result has several consequences. Firstly, planar k-trees admit 1-bend box-orthogonal drawings with boxes of size ⌈bkΔ⌉×⌈bkΔ⌉ , which generalizes a result of Tayu, Nomura, and Ueno. Secondly, they admit 1-bend polyline drawings with 2⌈bkΔ⌉ slopes, which is significantly smaller than the 2Δ upper bound established by Keszegh, Pach, and Pálvölgyi for arbitrary planar graphs.

Item Type: Conference Paper
Classifications: Z Theory > Z.500 Representations
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1368

Actions (login required)

View Item View Item