On Balanced Contact RepresentationsDurocher, Stephane and Mondal, Debajyoti (2013) On Balanced Contact Representations. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 143154(Official URL: http://dx.doi.org/10.1007/9783319038414_13). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_13
AbstractIn a contact representation of a planar graph G, each vertex is represented as an axisaligned plus shape consisting of two intersecting line segments (or equivalently, four axisaligned 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 cbalanced representation, c ≤ 1, every arm can touch at most ⌈cΔ⌉ other arms, where Δ is the maximum degree of G. The widely studied T and Lcontact representations are cbalanced representations, where c could be as large as 1. In contrast, the goal in a cbalanced representation is to minimize c. Let c k , where k ∈ {2,3}, be the smallest c such that every planar ktree has a cbalanced 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 ktrees admit 1bend boxorthogonal drawings with boxes of size ⌈bkΔ⌉×⌈bkΔ⌉ , which generalizes a result of Tayu, Nomura, and Ueno. Secondly, they admit 1bend 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.
Actions (login required)
