Interval representations of planar graphs (Q1077425): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0095-8956(86)90061-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1971244706 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Representing a planar graph by vertical lines joining different levels / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4138414 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The interval number of a planar graph: Three intervals suffice / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3216670 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3672006 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Diagrams Representing Maps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3684157 / rank | |||
Normal rank |
Latest revision as of 14:45, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Interval representations of planar graphs |
scientific article |
Statements
Interval representations of planar graphs (English)
0 references
1986
0 references
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)\).
0 references
interval representation
0 references
d-dimensional closed interval
0 references
intersection graph
0 references
planar graph
0 references
strict 3-box graph
0 references