Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-066-86
Planarity Testing of Doubly Periodic Infinite Graphs
Authors: Iwano, Kazuo, Steiglitz, Kenneth
Date:December 1986
Pages:27
Download Formats: [PDF]
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 arise 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 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 asymptotically no more difficult than planarity testing of finite graphs, and thus can be done in linear time.