{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T14:13:14Z","timestamp":1697983994985},"reference-count":22,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":6614,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1988,9]]},"abstract":"Abstract<\/jats:title>This paper describes an efficient way to test the VAP\u2010free<\/jats:italic> (Vertex Accumulation Point free) planarity of one\u2010 and two\u2010dimensional dynamic graphs. Dynamic graphs<\/jats:italic> are infinite graphs consisting of an infinite number of basic cells connected regularly according to labels in a finite graph called a static graph.<\/jats:italic> Dynamic graphs arize in the design of highly regular VLSI circuits, such as systolic arrays and digital signal processing chips. We show that VAP\u2010free planarity testing of dynamic graphs can be done efficiently by making use of their regularity. First, we will establish necessary conditions for VAP\u2010free 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\u2010free planar. From this it follows that VAP\u2010free planarity testing of one\u2010 and two\u2010dimensional dynamic graphs is asymptomically no more difficult than planarity testing of finite graphs, and thus can be done in linear time.<\/jats:p>","DOI":"10.1002\/net.3230180307","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T23:23:15Z","timestamp":1178925795000},"page":"205-222","source":"Crossref","is-referenced-by-count":10,"title":["Planarity testing of doubly periodic infinite graphs"],"prefix":"10.1002","volume":"18","author":[{"given":"Kazuo","family":"Iwano","sequence":"first","affiliation":[]},{"given":"Kenneth","family":"Steiglitz","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Topological Spaces","author":"Berge C.","year":"1963"},{"key":"e_1_2_1_3_2","volume-title":"CMU Conference on VLSI Systems and Computations","author":"Cappello P. R.","year":"1981"},{"key":"e_1_2_1_4_2","volume-title":"Graph Theory: An Algorithmic Approach","author":"Christofides N.","year":"1975"},{"key":"e_1_2_1_5_2","first-page":"77","volume-title":"Int. Symp. on Theory of Graphs","author":"Dantzig G. B.","year":"1967"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1385-7258(54)50043-0"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02566098"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662157.008"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01899579"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_11_2","unstructured":"K.IwanoandK.Steiglitz A semiring on convex polygons and zero\u2010sum cycle problems. Tech. Rep. CS\u2010TR\u2010053\u201086 Computer Science Dept. Princeton Univ. Princeton N.J. Sept.1986."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1986.1164923"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"K.IwanoandK.Steiglitz 1987a. Testing for cycles in infinite graphs with periodic structure.Proc. 19th Annual ACM Symposium on Theory of Computing May1987 46\u201355.","DOI":"10.1145\/28395.28401"},{"key":"e_1_2_1_14_2","unstructured":"K.Iwano Two\u2010dimensional dynamic graphs and their VLSI applications.Ph. D. dissertation Department of Computer Science Princeton University Oct. 1987."},{"key":"e_1_2_1_15_2","first-page":"209","volume-title":"Symp. on Theory of Graphs","author":"Lawler E. L.","year":"1967"},{"key":"e_1_2_1_16_2","first-page":"215","volume-title":"Int. Symp. on Theory of Graphs","author":"Lempel A.","year":"1967"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/B978-0-12-566780-7.50022-2","volume-title":"Progress in Combinatorial Optimization","author":"Orlin J.","year":"1984"},{"key":"e_1_2_1_18_2","volume-title":"Progress in Combinatorial Optimization","author":"Pulleybank W. R.","year":"1984"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321485"},{"key":"e_1_2_1_20_2","volume-title":"Int. Symp. on Theory of Graphs","author":"Rosentiehl P.","year":"1967"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-16.3.411"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90083-0"},{"key":"e_1_2_1_23_2","volume-title":"Selected Topics in Graph Theory 2","author":"Thomassen C.","year":"1983"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230180307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230180307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T20:04:35Z","timestamp":1697918675000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230180307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,9]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1988,9]]}},"alternative-id":["10.1002\/net.3230180307"],"URL":"https:\/\/doi.org\/10.1002\/net.3230180307","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,9]]}}}