Unit-length Rectangular Drawings of Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929433556811776 |
|---|---|
| author | Alegria, Carlos Da Lozzo, Giordano Di Battista, Giuseppe Frati, Fabrizio Grosso, Fabrizio Patrignani, Maurizio |
| author_facet | Alegria, Carlos Da Lozzo, Giordano Di Battista, Giuseppe Frati, Fabrizio Grosso, Fabrizio Patrignani, Maurizio |
| contents | A rectangular drawing of a planar graph $G$ is a planar drawing of $G$ in which vertices are mapped to grid points, edges are mapped to horizontal and vertical straight-line segments, and faces are drawn as rectangles. Sometimes this latter constraint is relaxed for the outer face. In this paper, we study rectangular drawings in which the edges have unit length. We show a complexity dichotomy for the problem of deciding the existence of a unit-length rectangular drawing, depending on whether the outer face must also be drawn as a rectangle or not. Specifically, we prove that the problem is NP-complete for biconnected graphs when the drawing of the outer face is not required to be a rectangle, even if the sought drawing must respect a given planar embedding, whereas it is polynomial-time solvable, both in the fixed and the variable embedding settings, if the outer face is required to be drawn as a rectangle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_14142 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Unit-length Rectangular Drawings of Graphs Alegria, Carlos Da Lozzo, Giordano Di Battista, Giuseppe Frati, Fabrizio Grosso, Fabrizio Patrignani, Maurizio Computational Geometry Data Structures and Algorithms A rectangular drawing of a planar graph $G$ is a planar drawing of $G$ in which vertices are mapped to grid points, edges are mapped to horizontal and vertical straight-line segments, and faces are drawn as rectangles. Sometimes this latter constraint is relaxed for the outer face. In this paper, we study rectangular drawings in which the edges have unit length. We show a complexity dichotomy for the problem of deciding the existence of a unit-length rectangular drawing, depending on whether the outer face must also be drawn as a rectangle or not. Specifically, we prove that the problem is NP-complete for biconnected graphs when the drawing of the outer face is not required to be a rectangle, even if the sought drawing must respect a given planar embedding, whereas it is polynomial-time solvable, both in the fixed and the variable embedding settings, if the outer face is required to be drawn as a rectangle. |
| title | Unit-length Rectangular Drawings of Graphs |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2208.14142 |