Embedding rectilinear graphs in linear time (Q1111399): Difference between revisions

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.

0 references

zbMATH Keywords

graph embedding

0 references

linear-time algorithm

0 references

rectilinear graphs

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0020-0190(88)90032-4

0 references

cites work

Automata and Labyrinths

0 references

Q3911393

0 references

Q3674695

0 references

The embeddings of a graph—A survey

0 references

On Embedding a Graph in the Grid with the Minimum Number of Bends

0 references

Rectilinear Graphs and Their Embeddings

0 references

Identifiers

zbMATH Open document ID

0658.68086

0 references

DOI

10.1016/0020-0190(88)90032-4

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1111399

@@ Property / cites work @@
+Automata and Labyrinths
@@ Property / cites work: Automata and Labyrinths / rank @@
+Normal rank
@@ Property / cites work @@
+Q3911393
@@ Property / cites work: Q3911393 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3674695
@@ Property / cites work: Q3674695 / rank @@
+Normal rank
@@ Property / cites work @@
+The embeddings of a graph—A survey
@@ Property / cites work: The embeddings of a graph—A survey / rank @@
+Normal rank
@@ Property / cites work @@
+On Embedding a Graph in the Grid with the Minimum Number of Bends
+Normal rank
@@ Property / cites work @@
+Rectilinear Graphs and Their Embeddings
@@ Property / cites work: Rectilinear Graphs and Their Embeddings / rank @@
+Normal rank