On representations of some thickness-two graphs
type: Item
instance of: scholarly article
title: On representations of some thickness-two graphs
zbMATH Open document ID: 0953.68116
DOI: 10.1016/S0925-7721(99)00018-8
author: Joan P. Hutchinson
author: Thomas C. Shermer
author: Andrew Vince
published in: Computational Geometry
publication date: 2000-01-17T00:00:00Z
review text: 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.
reviewed by: Charles J. Colbourn
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 1389792
zbMATH Keywords: rectangle-visibility graphs
MaRDI profile type: Publication
Wikidata QID: Q127579718
full work available at URL: s0925-7721(99)00018-8
OpenAlex ID: W2000514873
description: scientific article; zbMATH DE number 1389792