planar

providers: ISGCI

Definition: Has an embedding with vertices being points, edges being curves between respective points, which is planar, i.e., no curves cross each other.

Relations

Other		Relation from	Relation to
acyclic chromatic number	red■	exclusion	upper bound
admissibility	red■	exclusion	upper bound
arboricity	red■	exclusion	upper bound
average degree	red■	exclusion	upper bound
average distance	blue■	exclusion	unbounded
bandwidth	blue■	exclusion	unbounded
bipartite	blue■	exclusion	exclusion
bipartite number	blue■	exclusion	unbounded
bisection bandwidth	blue■	exclusion	unbounded
block	blue■	exclusion	exclusion
book thickness	red■	exclusion	upper bound
boolean width	blue■	exclusion	unbounded
bounded components	blue■	exclusion	unbounded
bounded expansion	red■	exclusion	upper bound
boxicity	red■	exclusion	upper bound
branch width	blue■	exclusion	unbounded
c-closure	magenta■	exclusion	unknown to HOPS
carving-width	blue■	exclusion	unbounded
chi-bounded	magenta■	exclusion	unknown to HOPS
chordal	blue■	exclusion	exclusion
chordality	red■	exclusion	upper bound
chromatic number	red■	exclusion	upper bound
clique cover number	blue■	exclusion	unbounded
clique-tree-width	blue■	exclusion	unbounded
clique-width	blue■	exclusion	unbounded
cluster	blue■	exclusion	exclusion
co-cluster	blue■	exclusion	exclusion
cograph	blue■	exclusion	exclusion
complete	blue■	exclusion	exclusion
connected	magenta■	exclusion	unknown to HOPS
contraction complexity	blue■	exclusion	unbounded
cutwidth	blue■	exclusion	unbounded
cycle	cyan■	unknown to HOPS	exclusion
cycles	cyan■	unknown to HOPS	exclusion
d-admissibility	red■	exclusion	upper bound
d-path-free	blue■	exclusion	unbounded
degeneracy	red■	exclusion	upper bound
degree treewidth	blue■	exclusion	unbounded
diameter	blue■	exclusion	unbounded
diameter+max degree	blue■	exclusion	unbounded
distance to bipartite	blue■	exclusion	unbounded
distance to block	blue■	exclusion	unbounded
distance to bounded components	blue■	exclusion	unbounded
distance to chordal	blue■	exclusion	unbounded
distance to cluster	blue■	exclusion	unbounded
distance to co-cluster	blue■	exclusion	unbounded
distance to cograph	blue■	exclusion	unbounded
distance to complete	blue■	exclusion	unbounded
distance to edgeless	blue■	exclusion	unbounded
distance to forest	blue■	exclusion	unbounded
distance to interval	blue■	exclusion	unbounded
distance to linear forest	blue■	exclusion	unbounded
distance to maximum degree	magenta■	exclusion	unknown to HOPS
distance to outerplanar	blue■	exclusion	unbounded
distance to perfect	blue■	exclusion	unbounded
distance to planar	red■	exclusion	upper bound
distance to stars	blue■	exclusion	unbounded
domatic number	red■	exclusion	upper bound
domination number	blue■	exclusion	unbounded
domino treewidth	blue■	exclusion	unbounded
edge clique cover number	blue■	exclusion	unbounded
edge connectivity	red■	exclusion	upper bound
edge-cut width	blue■	exclusion	unbounded
edge-treewidth	blue■	exclusion	unbounded
edgeless	cyan■	unknown to HOPS	avoids
excluded minor	red■	exclusion	upper bound
excluded planar minor	cyan■	unknown to HOPS	avoids
excluded top-minor	red■	exclusion	upper bound
feedback edge set	blue■	exclusion	unbounded
feedback vertex set	blue■	exclusion	unbounded
flip-width	red■	exclusion	upper bound
forest	cyan■	unknown to HOPS	exclusion
genus	red■	exclusion	upper bound
grid	green■	inclusion	exclusion
h-index	magenta■	exclusion	unknown to HOPS
interval	blue■	exclusion	exclusion
iterated type partitions	blue■	exclusion	unbounded
linear clique-width	blue■	exclusion	unbounded
linear forest	cyan■	unknown to HOPS	exclusion
linear NLC-width	blue■	exclusion	unbounded
linear rank-width	blue■	exclusion	unbounded
maximum clique	red■	exclusion	upper bound
maximum degree	blue■	exclusion	unbounded
maximum independent set	blue■	exclusion	unbounded
maximum induced matching	blue■	exclusion	unbounded
maximum leaf number	blue■	exclusion	unbounded
maximum matching	blue■	exclusion	unbounded
maximum matching on bipartite graphs	cyan■	unknown to HOPS	unbounded
merge-width	red■	exclusion	upper bound
mim-width	magenta■	exclusion	unknown to HOPS
minimum degree	red■	exclusion	upper bound
mm-width	blue■	exclusion	unbounded
modular-width	blue■	exclusion	unbounded
module-width	blue■	exclusion	unbounded
monadically dependent	red■	exclusion	upper bound
monadically stable	red■	exclusion	upper bound
neighborhood diversity	blue■	exclusion	unbounded
NLC-width	blue■	exclusion	unbounded
NLCT-width	blue■	exclusion	unbounded
nowhere dense	red■	exclusion	upper bound
odd cycle transversal	blue■	exclusion	unbounded
outerplanar	green■	inclusion	exclusion
overlap treewidth	blue■	exclusion	unbounded
path	green■	upper bound	exclusion
pathwidth	blue■	exclusion	unbounded
pathwidth+maxdegree	blue■	exclusion	unbounded
perfect	blue■	exclusion	exclusion
planar	yellow■	equal	equal
radius-inf flip-width	blue■	exclusion	unbounded
radius-r flip-width	red■	exclusion	upper bound
rank-width	blue■	exclusion	unbounded
series-parallel	gray■	unknown to HOPS	unknown to HOPS
shrub-depth	blue■	exclusion	unbounded
sim-width	magenta■	exclusion	unknown to HOPS
size	blue■	exclusion	unbounded
slim tree-cut width	blue■	exclusion	unbounded
sparse twin-width	red■	exclusion	upper bound
star	cyan■	unknown to HOPS	exclusion
stars	cyan■	unknown to HOPS	exclusion
strong coloring number	red■	exclusion	upper bound
strong d-coloring number	red■	exclusion	upper bound
strong inf-coloring number	blue■	exclusion	unbounded
topological bandwidth	blue■	exclusion	unbounded
tree	cyan■	unknown to HOPS	exclusion
tree-cut width	blue■	exclusion	unbounded
tree-independence number	magenta■	exclusion	unknown to HOPS
tree-partition-width	blue■	exclusion	unbounded
treebandwidth	blue■	exclusion	unbounded
treedepth	blue■	exclusion	unbounded
treelength	magenta■	exclusion	unknown to HOPS
treespan	blue■	exclusion	unbounded
treewidth	blue■	exclusion	unbounded
twin-cover number	blue■	exclusion	unbounded
twin-width	red■	exclusion	upper bound
vertex connectivity	gray■	unknown to HOPS	unknown to HOPS
vertex cover	blue■	exclusion	unbounded
vertex integrity	blue■	exclusion	unbounded
weak coloring number	red■	exclusion	upper bound
weak d-coloring number	red■	exclusion	upper bound
weak inf-coloring number	blue■	exclusion	unbounded
weakly sparse	red■	exclusion	upper bound
weakly sparse and merge width	red■	exclusion	upper bound

Results

2017 Graph Theory by Diestel
- page 89 : planar – When we draw a graph on a piece of paper, we naturally try to do this as transparently as possible. One obvious way to limit the mess created by all the lines is to avoid intersections. … Graphs drawn in this way are called \emph{plane graphs}; abstract graphs that can be drawn in this way are called \emph{planar}.
unknown source
- planar upper bounds excluded minor by a constant
- planar upper bounds genus by a constant
- graph class planar is not constant maximum degree
- graph class planar is not constant distance to perfect
assumed
- graph class outerplanar has contained in planar
- graph class planar does not have contained in outerplanar
- graph class grid has contained in planar
- graph class planar does not have contained in grid
- planar upper bounds distance to planar by a constant – by definition
- graph classes with bounded size do not have contained in planar – By definition
- planar is equivalent to planar – assumed