Open AccessRefining the Hierarchies of Classes of Geometric Intersection Graphs
Author(s) -
Sergio Cabello,
Miha Jejčič
Publication year - 2017
Publication title -
the electronic journal of combinatorics/the journal of combinatorics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.703
H-Index - 52
eISSN - 1097-1440
pISSN - 1077-8926
DOI - 10.37236/6040
Subject(s) - combinatorics , mathematics , intersection (aeronautics) , indifference graph , chordal graph , subdivision , subclass , pathwidth , discrete mathematics , intersection graph , class (philosophy) , integer (computer science) , graph , line graph , computer science , archaeology , artificial intelligence , biology , antibody , engineering , immunology , history , programming language , aerospace engineering
We analyse properties of geometric intersection graphs to show the strict containment between some natural classes of geometric intersection graphs. In particular, we show the following properties:A graph $G$ is outerplanar if and only if the 1-subdivision of $G$ is outer-segment.For each integer $k\ge 1$, the class of intersection graphs of segments with $k$ different lengths is a strict subclass of the class of intersection graphs of segments with $k+1$ different lengths.For each integer $k\ge 1$, the class of intersection graphs of disks with $k$ different sizes is a strict subclass of the class of intersection graphs of disks with $k+1$ different sizes.The class of outer-segment graphs is a strict subclass of the class of outer-string graphs.