Premium
Planarity testing of doubly periodic infinite graphs
Author(s) -
Iwano Kazuo,
Steiglitz Kenneth
Publication year - 1988
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230180307
Subject(s) - planarity testing , book embedding , chordal graph , 1 planar graph , indifference graph , vertex (graph theory) , combinatorics , planar graph , computer science , pathwidth , discrete mathematics , mathematics , graph , line graph
Abstract This paper describes an efficient way to test the VAP‐free (Vertex Accumulation Point free) planarity of one‐ and two‐dimensional dynamic graphs. Dynamic graphs are infinite graphs consisting of an infinite number of basic cells connected regularly according to labels in a finite graph called a static graph. Dynamic graphs arize in the design of highly regular VLSI circuits, such as systolic arrays and digital signal processing chips. We show that VAP‐free planarity testing of dynamic graphs can be done efficiently by making use of their regularity. First, we will establish necessary conditions for VAP‐free planarity of dynamic graphs. Then we show the existence of a small finite graph which is planar if and only if the original dynamic graph is VAP‐free planar. From this it follows that VAP‐free planarity testing of one‐ and two‐dimensional dynamic graphs is asymptomically no more difficult than planarity testing of finite graphs, and thus can be done in linear time.