The efficient recognition on net-extensibility of graphs

MaRDI QIDQ687910zbMATH OpenFDO

Authors Yanpei Liu

Publication date 28 June 1994

Published in Chinese Science Bulletin (Search for Journal in Brave)

zbMATH Keywords

algorithmembeddingnet-extensionplane

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

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.

Recommendations

• Publication:4724655
• scientific article; zbMATH DE number 432759
• Optimally extending bistandard graphs on the orthogonal grid (extended abstract)
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• How to draw a planar graph on a grid

Cited in

(3)

• Some combinatorial optimization problems arising from VLSI circuit design
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• scientific article; zbMATH DE number 3997826 (Why is no real title available?)

This page was built for publication: The efficient recognition on net-extensibility of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q687910)