Simple Geometrical Intersection Graphs

DOI10.1007/978-3-540-77891-2_3MaRDI QIDQ5452149zbMATH OpenOpenAlexFDO

Authors 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

graph isomorphismgrid intersection graphsHamiltonian path probleminterval graphs

Mathematics Subject Classification ID

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

Recommendations

• Tractabilities and intractabilities on geometric intersection graphs
• Characterizing intersection classes of graphs
• Algorithmic aspects of intersection graphs and representation hypergraphs
• scientific article; zbMATH DE number 32301
• scientific article; zbMATH DE number 1028234

Cites work

• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Efficient graph representations
• Finding Hamiltonian circuits in interval graphs
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Interval bigraphs and circular arc graphs
• On testing isomorphism of permutation graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• 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
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Topics in Intersection Graph Theory

Cited in

(13)

• Algorithmic aspects of intersection graphs and representation hypergraphs
• The QAP-polytope and the graph isomorphism problem
• Tractabilities and intractabilities on geometric intersection graphs
• The longest path problem is polynomial on cocomparability graphs
• The balanced connected subgraph problem for geometric intersection graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• On the isomorphism problem for Helly circular-arc graphs
• The longest path problem is polynomial on cocomparability graphs
• scientific article; zbMATH DE number 32301 (Why is no real title available?)
• scientific article; zbMATH DE number 1028234 (Why is no real title available?)
• scientific article; zbMATH DE number 1156662 (Why is no real title available?)
• Optimal grid representations
• On unit grid intersection graphs and several other intersection graph classes

This page was built for publication: Simple Geometrical Intersection Graphs

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