Simple Geometrical Intersection Graphs

DOI10.1007/978-3-540-77891-2_3zbMath1132.05320OpenAlexW1553648594MaRDI QIDQ5452149

Ryuhei Uehara

Publication date: 25 March 2008

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77891-2_3

zbMATH Keywords

interval graphsgraph isomorphismHamiltonian path problemgrid intersection graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

The QAP-polytope and the graph isomorphism problem ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ On the isomorphism problem for Helly circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding Hamiltonian circuits in interval graphs
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Efficient graph representations
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Algorithmic graph theory and perfect graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• On testing isomorphism of permutation graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Topics in Intersection Graph Theory
• Interval bigraphs and circular arc graphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Algorithms and Computation

This page was built for publication: Simple Geometrical Intersection Graphs