Embedding rectilinear graphs in linear time
type: Item
instance of: scholarly article
title: Embedding rectilinear graphs in linear time
zbMATH Open document ID: 0658.68086
DOI: 10.1016/0020-0190(88)90032-4
author: Frank Hoffmann
author: Klaus Kriegel
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: A linear-time algorithm is presented to recognize and embed rectilinear graphs which are embeddable on the plane. Previously, only the \(O(n^ 2)\) time algorithm of \textit{G. Vijayan} and \textit{A. Wigderson} [SIAM J. Comput. 14, 355-372 (1985; Zbl 0568.05024)] was known. The algorithm described here uses a different and surprisingly simple strategy.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 4076654
zbMATH Keywords: graph embedding
zbMATH Keywords: linear-time algorithm
zbMATH Keywords: rectilinear graphs
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90032-4
OpenAlex ID: W2166449951
cites work: Automata and Labyrinths
cites work: Q3911393
cites work: Q3674695
cites work: The embeddings of a graph—A survey
cites work: On Embedding a Graph in the Grid with the Minimum Number of Bends
cites work: Rectilinear Graphs and Their Embeddings
description: scientific article; zbMATH DE number 4076654