Interval representations of planar graphs
From MaRDI portal
A graph is said to be a strict d-box graph if it is an intersection graph such that the sets are closed d-boxes \((=d\)-dimensional closed intervals) in \(R^ d\), no two of which have an interior point in common and such that two boxes which intersect have precisely a (d-1)-box in common. The author proves that every planar graph is a strict 3-box graph, and characterizes the 2-box graphs; these turn out to be precisely the proper subgraphs of 4-connected planar triangulations. In the case when more than one rectangle is allowed to represent a vertex, the author shows that two rectangles for each vertex are sufficient to represent any planar graph \((d=2)\).
Recommendations
Cites work
- scientific article; zbMATH DE number 3882450 (Why is no real title available?)
- scientific article; zbMATH DE number 3825834 (Why is no real title available?)
- scientific article; zbMATH DE number 3906537 (Why is no real title available?)
- scientific article; zbMATH DE number 3566474 (Why is no real title available?)
- On Diagrams Representing Maps
- Representing a planar graph by vertical lines joining different levels
- The interval number of a planar graph: Three intervals suffice
Cited in
(70)- Boxicity of graphs with bounded degree
- Cubicity, boxicity, and vertex cover
- An upper bound for cubicity in terms of boxicity
- Localized and compact data-structure for comparability graphs
- Boxicity of Halin graphs
- On the cubicity of certain graphs
- On the cubicity of interval graphs
- On grid intersection graphs
- Representations of graphs and networks (coding, layouts and embeddings)
- Intersection dimensions of graph classes
- On intersection representations of co-planar graphs
- Dushnik-Miller dimension of contact systems of d-dimensional boxes
- Sublinear approximation algorithms for boxicity and related problems
- Local and union boxicity
- Fully dynamic representations of interval graphs
- Representing graphs as the intersection of cographs and threshold graphs
- Local boxicity
- Finding geometric representations of apex graphs is NP-hard
- Representing graphs and hypergraphs by touching polygons in 3D
- Intersection dimension and graph invariants
- The interval number of a planar graph is at most three
- Lower bounds for boxicity
- The dimension of posets with planar cover graphs.
- Boxicity of graphs on surfaces
- Chronological rectangle digraphs which are two-terminal series-parallel
- Boxicity and maximum degree
- Boxicity of series-parallel graphs
- Cubicity, degeneracy, and crossing number
- Boxicity and treewidth
- Cubicity of interval graphs and the claw number
- Separation dimension of graphs and hypergraphs
- Cubicity of interval graphs and the claw number
- Distance Labeling for Permutation Graphs
- Threshold-coloring and unit-cube contact representation of planar graphs
- Contact representations of graphs in 3D
- On the Cubicity of Interval Graphs
- On Representation of Planar Graphs by Segments
- Matchings, coverings, and Castelnuovo-Mumford regularity
- Boxicity of line graphs
- Orthogonal tree decompositions of graphs
- Bounds for the boxicity of Mycielski graphs
- Boxicity and topological invariants
- Morphing Contact Representations of Graphs
- Better bounds for poset dimension and boxicity
- p-box: a new graph model
- Box representations of embedded graphs
- Shorter Labeling Schemes for Planar Graphs
- Morphing triangle contact representations of triangulations
- Algorithms and complexity for geodetic sets on partial grids
- scientific article; zbMATH DE number 7765365 (Why is no real title available?)
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- Finding geometric representations of apex graphs is \textsf{NP}-hard
- Side-contact representations with convex polygons in 3D: new results for complete bipartite graphs
- A note on lower bounds for boxicity of graphs
- Boxicity of leaf powers
- Chordal bipartite graphs with high boxicity
- Boxicity of circular arc graphs
- Contact graphs of boxes with unidirectional contacts
- Boxicity, poset dimension, and excluded minors
- Boxicity and cubicity of a subclass of divisor graphs and power graphs of cyclic groups
- A survey on the boxicity and cubicity of graphs
- Approximation of MWIS on geometric intersection graphs
- Plattenbauten: touching rectangles in space
- On generalizations of pairwise compatibility graphs
- Boxicity of zero divisor graphs
- A constant factor approximation algorithm for boxicity of circular arc graphs
- Geometric representation of graphs in low dimension using axis parallel boxes
- Bounds on the Stanley depth and Stanley regularity of edge ideals of clutters
- Boxicity and cubicity of asteroidal triple free graphs
- The cubicity of hypercube graphs
This page was built for publication: Interval representations of planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077425)
