Spanning 2connected subgraphs of alphabet graphs, special classes of grid graphs
Salman, A.N.M. and Baskoro, E.T. and Broersma, H.J. (2002) Spanning 2connected subgraphs of alphabet graphs, special classes of grid graphs. [Report]

PDF
205kB 
Abstract:  A grid graph is a finite induced subgraph of the infinite 2dimensional grid defined by and all edges between pairs of vertices from at Euclidean distance precisely 1. A natural drawing of is obtained by drawing its vertices in according to their coordinates. Apart from the outer face, all (inner) faces with area exceeding one (not bounded by a 4cycle) in a natural drawing of are called the holes of . We define 26 classes of grid graphs called alphabet graphs, with no or a few holes. We determine which of the alphabet graphs contain a Hamilton cycle, i.e. a cycle containing all vertices, and solve the problem of determining a spanning 2connected subgraph with as few edges as possible for all alphabet graphs. 
Item Type:  Report 
Additional information:  Imported from MEMORANDA 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65816 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page