Recognition and drawing of stick graphs

DOI10.1007/978-3-030-04414-5_21zbMath1435.68229arXiv1808.10005OpenAlexW2888996674WikidataQ127354497 ScholiaQ127354497MaRDI QIDQ5915944

Felice De Luca, Stephen G. Kobourov, Debajyoti Mondal, Md. Iqbal Hossain, Anna Lubiw

Publication date: 15 February 2019

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.10005

zbMATH Keywords

bipartite graphsgraph drawingintersection graphsstick graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Forced pairs in \(A\)-Stick graphs ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Recognition and drawing of stick graphs

Cites Work

• Max point-tolerance graphs
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• On orthogonal ray graphs
• Orthogonal segment stabbing
• Grid intersection graphs and order dimension
• The simultaneous consecutive ones problem
• Bipartite permutation graphs
• On the Ferrers dimension of a digraph
• On grid intersection graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A special planar satisfiability problem and a consequence of its NP- completeness
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Intersection graphs of rays and grounded segments
• Permuting matrices to avoid forbidden submatrices
• Stick graphs with length constraints
• Doubly lexical ordering of dense 0--1 matrices
• On the Recognition of Four-Directional Orthogonal Ray Graphs
• Ordering without Forbidden Patterns
• Jump Number of Two-Directional Orthogonal Ray Graphs
• The LBFS Structure and Recognition of Interval Graphs
• Doubly Lexical Orderings of Matrices
• Interval digraphs: An analogue of interval graphs
• Every planar graph is the intersection graph of segments in the plane
• (c-)AND: A new graph model
• Efficient parallel algorithms for bipartite permutation graphs
• Intersection Dimension of Bipartite Graphs
• Refining the hierarchies of classes of geometric intersection graphs
• Recognition and drawing of stick graphs