Geodesic
A Note on Minimum-Segment Drawings of Planar Graphs
Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 301-328.

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

A straight-line drawing of a planar graph G is a planar drawing of G such that each vertex is mapped to a point on the Euclidean plane, each edge is drawn as a straight line segment, and no two edges intersect except possibly at a common endpoint. A segment in a straight-line drawing is a maximal set of edges that form a straight line segment. A k-segment drawing of G is a straight-line drawing of G such that the number of segments is at most k. A plane graph is a fixed planar embedding of a planar graph. In this paper we prove that it is NP-hard to determine whether a plane graph G with maximum degree four has a k-segment drawing, where k ≥ 3. The problem remains NP-hard when the drawing is constrained to be convex. We also prove that given a partial drawing Γ of a plane graph G, it is NP-hard to determine whether there exists a k-segment drawing of G that contains all the segments specified in Γ, even when G is outerplanar. The problem remains NP-hard for planar graphs with maximum degree three in R3 when given subsets of the vertices are restricted to be coplanar. Finally, we investigate a worst-case lower bound on the number of segments required by straight-line drawings of arbitrary spanning trees of a given planar graph.
DOI : 10.7155/jgaa.00295
Keywords: planar graphs, straight-line drawings, NP-complete, minimum-segment drawings 
@article{JGAA_2013_17_3_a6,
     author = {Stephane Durocher and Debajyoti Mondal and Rahnuma Islam Nishat and Sue Whitesides},
     title = {A {Note} on {Minimum-Segment} {Drawings} of {Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {301--328},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2013},
     doi = {10.7155/jgaa.00295},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00295/}
}
TY  - JOUR
AU  - Stephane Durocher
AU  - Debajyoti Mondal
AU  - Rahnuma Islam Nishat
AU  - Sue Whitesides
TI  - A Note on Minimum-Segment Drawings of Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 301
EP  - 328
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00295/
DO  - 10.7155/jgaa.00295
LA  - en
ID  - JGAA_2013_17_3_a6
ER  - 
%0 Journal Article
%A Stephane Durocher
%A Debajyoti Mondal
%A Rahnuma Islam Nishat
%A Sue Whitesides
%T A Note on Minimum-Segment Drawings of Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2013
%P 301-328
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00295/
%R 10.7155/jgaa.00295
%G en
%F JGAA_2013_17_3_a6
Stephane Durocher; Debajyoti Mondal; Rahnuma Islam Nishat; Sue Whitesides. A Note on Minimum-Segment Drawings of Planar Graphs. Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 301-328. doi : 10.7155/jgaa.00295. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00295/

Cité par Sources :