The efficient recognition on net-extensibility of graphs (Q687910): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:59, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The efficient recognition on net-extensibility of graphs |
scientific article |
Statements
The efficient recognition on net-extensibility of graphs (English)
0 references
28 June 1994
0 references
Let \(\mu(G)\) be an embedding of \(G\) in the plane. A net-extension of \(\mu(G)\) is an embedding of \(G\) which is topologically equivalent to \(\mu(G)\) where the vertices are integer grid points and the edges are either horizontal or vertical paths. The author gives an algorithm for determining when an embedding \(\mu(G)\) has a net-extension. The algorithm develops a system of equations which records the angles of the desired net-extension, then translates these equations to a transportation problem.
0 references
embedding
0 references
plane
0 references
net-extension
0 references
algorithm
0 references