On Boolean characterizations of planarity and planar embeddings of graphs

DOI10.1007/BF02216821MaRDI QIDQ2276969zbMATH OpenOpenAlexFDO

Authors Yanpei Liu

Publication date 1990

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02216821

zbMATH Keywords

finding a planar imbeddingmaximal planar subgraphsplanarity characterizationplanarity obstaclesplanarity testingquadratic Boolean equation

Mathematics Subject Classification ID

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

Review text

The author introduces a new planarity characterization for graphs, involving the solution of a quadratic Boolean equation. He then discusses seven combinatorially distinct configurations, called planarity obstacles, which lead to a graph whose order and size are linear functions of those of the original graph. Testing for planarity and finding a planar imbedding of the original graph can be realized algorithmically from the second graph, in linear time. A decomposition of a non-planar graph into ``T-maximal planar subgraphs (where T is a spanning tree) is also provided.

Recommendations

• Boolean planarity characterization of graphs
• Boolean approach to planar embeddings of a graph
• On the linearity of testing planarity of graphs
• Another characterisation of planar graphs
• A new planarity test

Cites work

• A Depth-First-Search Characterization of Planarity
• A new approach to the linearity of testing planarity of graphs
• A structural characterization of planar combinatorial graphs
• Efficient Planarity Testing
• scientific article; zbMATH DE number 3116364 (Why is no real title available?)
• scientific article; zbMATH DE number 3165199 (Why is no real title available?)
• scientific article; zbMATH DE number 3249560 (Why is no real title available?)
• scientific article; zbMATH DE number 3024665 (Why is no real title available?)
• Non-Separable and Planar Graphs
• On the linearity of testing planarity of graphs
• Planar Graphs
• Preuve Algebrique Du Critere De Planarite De Wu-Liu
• Toward a theory of crossing numbers

Cited in

(7)

• Boolean approaches to graph embeddings related to VLSI
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Another characterisation of planar graphs
• scientific article; zbMATH DE number 431506 (Why is no real title available?)
• Boolean planarity characterization of graphs
• Boolean approach to planar embeddings of a graph
• Characterizing planarity using theta graphs

This page was built for publication: On Boolean characterizations of planarity and planar embeddings of graphs

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