On the Complexity of the Planar Slope Number Problem

DOI10.7155/jgaa.00411zbMath1358.05078OpenAlexW2573654584MaRDI QIDQ2971391

Udo Hoffmann

Publication date: 5 April 2017

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

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)

Related Items

Upward Planar Drawings with Three and More Slopes, The Complexity of Drawing a Graph in a Polygonal Region, Upward planar drawings with two slopes, Universal slope sets for 1-bend planar drawings, 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, Variants of the segment number of a graph, Level-planar drawings with few slopes, Level-planar drawings with few slopes, On the Complexity of Some Geometric Problems With Fixed Parameters

Cites Work

• Unnamed Item
• Unnamed Item
• The planar slope number of planar partial 3-trees of bounded degree
• Recognition and complexity of point visibility graphs
• Intersection graphs of segments
• Graph drawings with few slopes
• Outerplanar graph drawings with few slopes
• Bounded-degree graphs can have arbitrarily large slope numbers
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Realizability of Graphs and Linkages
• Planar and Plane Slope Number of Partial 2-Trees
• Drawing Graphs in the Plane with High Resolution
• The Intrinsic Spread of a Configuration in R d
• On the decidability of Diophantine problems in combinatorial geometry
• On the Angular Resolution of Planar Graphs
• Realization spaces of 4-polytopes are universal
• The Planar Slope Number of Subcubic Graphs
• Drawing Planar Graphs of Bounded Degree with Few Slopes