The parametrized complexity of the segment number

DOI10.1007/978-3-031-49275-4_7MaRDI QIDQ6618253zbMATH OpenFDO

Authors Sabine Cornelsen, Giordano Da Lozzo, Luca Grilli, Siddharth Gupta, Jan Kratochvíl, Alexander Wolff

Publication date 14 October 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49275-4_7

zbMATH Keywords

line cover numberparameterized complexitysegment numbervertex cover numbervisual complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A note on minimum-segment drawings of planar graphs
• An application of simultaneous diophantine approximation in combinatorial optimization
• Complexity of some geometric and topological problems
• Drawing graphs on few circles and few spheres
• Drawing graphs on few lines and few planes
• Drawing Graphs with Few Arcs
• Drawing planar cubic 3-connected graphs with few segments: algorithms \& experiments
• Drawing planar graphs with few geometric primitives
• Drawing planar graphs with few segments on a polynomial grid
• Drawing plane triangulations with few segments
• Drawings of planar graphs with few slopes and segments
• Experimental analysis of the accessibility of drawings with few segments
• Geometry Revealed
• Improved upper bounds for vertex cover
• Induced subgraphs of graphs with large chromatic number. VI. Banana trees
• Integer Programming with a Fixed Number of Variables
• Minimum Segment Drawings of Series-Parallel Graphs with the Maximum Degree Three
• Minkowski's Convex Body Theorem and Integer Programming
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Parameterized algorithms for book embedding problems
• Parameterized algorithms for queue layouts
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• The segment number: algorithms and universal lower bounds for some classes of planar graphs
• Variants of the segment number of a graph

Cited in

(1)

• Parameterized approaches to orthogonal compaction

This page was built for publication: The parametrized complexity of the segment number

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