On the complexity of the planar slope number problem

DOI10.7155/JGAA.00411MaRDI QIDQ2971391zbMATH OpenOpenAlexFDO

Authors Udo Hoffmann

Publication date 5 April 2017

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00411

zbMATH Keywords

crossing-free straight-line drawing of a graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Upward Planar Drawings with Three and More Slopes
• The planar slope number of planar partial 3-trees of bounded degree
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Drawings of planar graphs with few slopes and segments
• The Planar Slope Number of Subcubic Graphs

Cites work

• Bounded-degree graphs can have arbitrarily large slope numbers
• Drawing Graphs in the Plane with High Resolution
• Graph drawings with few slopes
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Intersection graphs of segments
• On the Angular Resolution of Planar Graphs
• On the computational complexity of upward and rectilinear planarity testing
• On the decidability of Diophantine problems in combinatorial geometry
• Outerplanar graph drawings with few slopes
• Planar and plane slope number of partial 2-trees
• Realizability of graphs and linkages
• Realization spaces of 4-polytopes are universal
• Recognition and complexity of point visibility graphs
• The Intrinsic Spread of a Configuration in R d
• The planar slope number of planar partial 3-trees of bounded degree
• The Planar Slope Number of Subcubic Graphs

Cited in

(16)

• Variants of the segment number of a graph
• Universal slope sets for 1-bend planar drawings
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• The complexity of drawing a graph in a polygonal region
• Upward planar drawings with two slopes
• NP-completeness of slope-constrained drawing of complete graphs
• The Planar Slope Number of Subcubic Graphs
• On the complexity of some geometric problems with fixed parameters
• Upward Planar Drawings with Three and More Slopes
• Level-planar drawings with few slopes
• Level-planar drawings with few slopes
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• The Complexity of Angular Resolution
• RAC-Drawability is ∃ℝ-complete and Related Results
• Topological art in simple galleries
• From planar via outerplanar to outerpath -- engineering NP-hardness constructions (poster abstract)

This page was built for publication: On the complexity of the planar slope number problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2971391)