Simple Geometrical Intersection Graphs

DOI10.1007/978-3-540-77891-2_3zbMATH Open1132.05320OpenAlexW1553648594MaRDI QIDQ5452149FDOQ5452149

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

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

zbMATH Keywords

interval graphsgraph isomorphismHamiltonian path problemgrid intersection graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Title not available (Why is that?)
• Finding Hamiltonian circuits in interval graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Title not available (Why is that?)
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Interval bigraphs and circular arc 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
• On testing isomorphism of permutation graphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Algorithms and Computation

Cited In (11)

• On the isomorphism problem for Helly circular-arc graphs
• The longest path problem is polynomial on cocomparability graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• The QAP-polytope and the graph isomorphism problem
• Tractabilities and intractabilities on geometric intersection graphs
• On unit grid intersection graphs and several other intersection graph classes
• Optimal grid representations
• The balanced connected subgraph problem for geometric intersection graphs
• The longest path problem is polynomial on cocomparability graphs
• Title not available (Why is that?)
• Algorithmic aspects of intersection graphs and representation hypergraphs

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)