Abstract | ||
---|---|---|
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 Delta +O(1)$, where $Delta$ 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 $cu003c1$ 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 $frac{deg(v)}{2}+ O(1)$. |
Year | Venue | Field |
---|---|---|
2017 | arXiv: Computational Geometry | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Dual polyhedron,Degree (graph theory),Mathematics,Planar graph |
DocType | Volume | Citations |
Journal | abs/1708.09560 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Therese Biedl | 1 | 902 | 106.36 |
Debajyoti Mondal | 2 | 93 | 27.33 |