On representations of some thickness-two graphs (Q1961382): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q127579718 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0925-7721(99)00018-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2000514873 / rank | |||
Normal rank |
Latest revision as of 08:53, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On representations of some thickness-two graphs |
scientific article |
Statements
On representations of some thickness-two graphs (English)
0 references
17 January 2000
0 references
Two classes of graphs with thickness two are examined. The first is the class of rectangle-visibility graphs, which are defined as graphs whose vertices are isothetic rectangles in the plane with adjacency defined by vertical or horizontal visibility. The second class consists of doubly linear graphs, those having a straight line embedding in which the edges can be partitioned into two sets so that each set induces a (straight line) planar embedding without edge crossings. It is shown that the maximum number of edges in an \(n\)-vertex graph in one of these classes is at most \(6n\)-20 (\(6n\)-18, respectively). Dense examples in both classes are constructed.
0 references
rectangle-visibility graphs
0 references