Radial Level Planarity: A Propositional Logic Approach - Softcover

Inhaltsangabe

Drawing graphs is a discipline in graph theory,dealing with the optimal representation of graphs. Animportant class of graphs are the planar graphs,which can be drawn without any intersecting edges.Such graphs are superior in terms of humanreadability. Radial level graphs are a specific classof graphs that only have edges between vertices ofdifferent levels, which are arranged in concentriccircles. The knowledge about the planarity of a graphenables the use of more efficient algorithms todisplay good representations. In this book, severalapproaches are discussed to describe the problem ofradial level planarity in a propositional logicframework. A model is introduced that describes theproblem as a SAT problem and for some types of graphseven as a 2-SAT problem, which is solvable in lineartime. The truth assignment of the variables describesthe non-intersecting embedding. Additionally, themodel is capable of introducing vertices-grouping,enabling the modelling of semantic rules. This bookis aiming for scientists that do research in thefields of graph drawing and/or propositional networksand theoretical informatics as well as for interestedstudents.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.