Год издания: 2008
Количество страниц: 144
В продаже с 18.01.2012
Как только книга Radial Level Planarity: A Propositional Logic Approach станет доступна для заказа в одном из интернет-магазинов, Вам на e-mail будет отправлено уведомление.Укажите e-mail для связи:
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...