Geodesic
Unit-length Rectangular Drawings of Graphs
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 403-437.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 combinatorial 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. Furthermore, we provide a linear-time algorithm for deciding whether a plane graph admits an embedding-preserving unit-length rectangular drawing if the drawing of the outer face is prescribed. As a by-product of our research, we provide the first polynomial-time algorithm to test whether a planar graph $G$ admits a rectangular drawing, for general instances of maximum degree $4$.
DOI : 10.7155/jgaa.v28i1.2996
Keywords: planarity, rectilinear drawing, rectangular faces, Grid graphs

Carlos Alegría 1 ; Giordano Da Lozzo 1 ; Giuseppe Di Battista 1 ; Fabrizio Frati 1 ; Fabrizio Grosso 1 ; Maurizio Patrignani 1

1 Roma Tre University 
@article{JGAA_2024_28_1_a17,
     author = {Carlos Alegr{\'\i}a and Giordano Da Lozzo and Giuseppe Di Battista and Fabrizio Frati and Fabrizio Grosso and Maurizio Patrignani},
     title = {Unit-length {Rectangular} {Drawings} of {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {403--437},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2996},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2996/}
}
TY  - JOUR
AU  - Carlos Alegría
AU  - Giordano Da Lozzo
AU  - Giuseppe Di Battista
AU  - Fabrizio Frati
AU  - Fabrizio Grosso
AU  - Maurizio Patrignani
TI  - Unit-length Rectangular Drawings of Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 403
EP  - 437
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2996/
DO  - 10.7155/jgaa.v28i1.2996
LA  - en
ID  - JGAA_2024_28_1_a17
ER  - 
%0 Journal Article
%A Carlos Alegría
%A Giordano Da Lozzo
%A Giuseppe Di Battista
%A Fabrizio Frati
%A Fabrizio Grosso
%A Maurizio Patrignani
%T Unit-length Rectangular Drawings of Graphs
%J Journal of Graph Algorithms and Applications
%D 2024
%P 403-437
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2996/
%R 10.7155/jgaa.v28i1.2996
%G en
%F JGAA_2024_28_1_a17
Carlos Alegría; Giordano Da Lozzo; Giuseppe Di Battista; Fabrizio Frati; Fabrizio Grosso; Maurizio Patrignani. Unit-length Rectangular Drawings of Graphs. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 403-437. doi : 10.7155/jgaa.v28i1.2996. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2996/

Cité par Sources :