z-logo
open-access-imgOpen Access
Refining 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
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom