Drawing graphs on rectangular grids (Q1902892): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing an st-numbering / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4028111 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Drawing planar graphs using the canonical ordering / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5596083 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3997942 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On minimal-node-cost planar embeddings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Universality considerations in VLSI circuits / rank | |||
Normal rank |
Latest revision as of 08:43, 24 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Drawing graphs on rectangular grids |
scientific article |
Statements
Drawing graphs on rectangular grids (English)
0 references
3 December 1996
0 references
The author considers the problem of embedding undirected graphs with \(n\) vertices of maximum degree 4 into rectangular grids. He presents an \(O(n^2)\)-algorithm that constructs an embedding for arbitrary 4-graphs into a \(2n \times 2n\) grid bending every edge at most twice. Firstly he constructs embeddings with at most three bends per wire into a \(2n \times 2n\) grid. Then the resulting embeddings can be modified to obtain at most two bends per wire without enlarging the grid area.
0 references
embedding
0 references
rectangular grids
0 references