2017/08/31 by Biedl, Therese, Mondal, Debajyoti
#68R10 #Computational Geometry (cs.CG) #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.1708.09560
A plus-contact representation of a planar graph G is called c-balanced if for every plus shape +v, the number of other plus shapes incident to each arm of +v is at most c Δ+O(1), where Δ is the maximum degree of G. Although small values of c have been achieved for a few subclasses of planar graphs (e.g., 2- and 3-trees), it is unknown whether c-balanced representations with c<1 exist for arbitrary planar graphs. In this paper we compute (1/2)-balanced plus-contact representations for all planar graphs that admit a rectangular dual. Our result implies that any graph with a rectangular dual has a 1-bend box-orthogonal drawings such that for each vertex v, the box representing v is a square of side length (deg(v))/(2)+ O(1).