42:
31:
135:
Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a
344:
112:
376:
graph for a finite set of points in the plane is produced by the grid obtained by intersections of all vertical and horizontal lines through each point of the set.
148:. Moreover, these terms are also commonly used for a finite section of the infinite graph, as in "an 8 × 8 square grid".
201:, and two vertices are connected by an edge whenever the corresponding points are at distance 1. In other words, it is a
424:
398:, although this graph is strictly different than the lattice graph described in this article. The valid moves of
155:
has also been given in the literature to various other kinds of graphs with some regular structure, such as the
69:
214:
156:
233:, the latter fact implies that the square grid graph is also a median graph. All square grid graphs are
273:
17:
88:
237:, which is easily verified by the fact that one can color the vertices in a checkerboard fashion.
548:
543:
8:
202:
121:
480:
450:
419:
399:
350:
45:
517:
354:
453:
380:
349:
Grid graphs are fundamental objects in the theory of graph minors because of the
234:
129:
81:
483:
160:
117:
537:
429:
402:
73:
34:
522:
505:
414:
384:
252:
230:
53:
387:
259:
245:
175:) is the graph whose vertices correspond to the points in the plane with
41:
391:
373:
218:
488:
458:
171:
A common type of lattice graph (known under different names, such as
125:
77:
30:
240:
A path graph may also be considered to be a grid graph on the grid
176:
27:
Graph whose embedding in a
Euclidean space forms a regular tiling
504:
Robertson, N.; Seymour, P.; Thomas, R. (November 1994).
503:
448:
276:
91:
478:
383:(the graph that represents all legal moves of the
369:is a graph that corresponds to a triangular grid.
338:
106:
535:
229: − 1 edges. Since a path graph is a
244:times 1. A 2 × 2 grid graph is a
474:
472:
470:
521:
510:Journal of Combinatorial Theory, Series B
94:
40:
29:
467:
442:
14:
536:
130:lattice in the group-theoretical sense
479:
449:
166:
128:that send the graph to itself is a
24:
506:"Quickly Excluding a Planar Graph"
25:
560:
425:Integer triangles in a 2D lattice
339:{\displaystyle h=2|V(H)|+4|E(H)|}
107:{\displaystyle \mathbb {R} ^{n}}
405:form the square lattice graph.
394:) is also sometimes called the
497:
360:
332:
328:
322:
315:
304:
300:
294:
287:
13:
1:
435:
208:
205:for the described point set.
353:. They play a major role in
7:
408:
215:Cartesian product of graphs
10:
565:
213:A square grid graph is a
126:bijective transformations
120:. This implies that the
355:bidimensionality theory
523:10.1006/jctb.1994.1073
351:grid exclusion theorem
340:
108:
49:
38:
367:triangular grid graph
341:
109:
44:
33:
274:
225: − 1 and
196:1, ...,
185:1, ...,
89:
203:unit distance graph
194:being in the range
183:being in the range
481:Weisstein, Eric W.
451:Weisstein, Eric W.
336:
104:
50:
39:
400:fairy chess piece
217:, namely, of two
173:square grid graph
167:Square grid graph
157:Cartesian product
16:(Redirected from
556:
528:
527:
525:
501:
495:
494:
493:
476:
465:
464:
463:
446:
345:
343:
342:
337:
335:
318:
307:
290:
200:
193:
189:
182:
115:
113:
111:
110:
105:
103:
102:
97:
21:
564:
563:
559:
558:
557:
555:
554:
553:
534:
533:
532:
531:
502:
498:
477:
468:
454:"Lattice graph"
447:
443:
438:
411:
363:
331:
314:
303:
286:
275:
272:
271:
266: ×
211:
195:
191:
184:
180:
169:
161:complete graphs
159:of a number of
98:
93:
92:
90:
87:
86:
84:
82:Euclidean space
46:Triangular grid
28:
23:
22:
15:
12:
11:
5:
562:
552:
551:
549:Graph families
546:
530:
529:
516:(2): 323–348.
496:
466:
440:
439:
437:
434:
433:
432:
427:
422:
420:Pick's theorem
417:
410:
407:
362:
359:
334:
330:
327:
324:
321:
317:
313:
310:
306:
302:
299:
296:
293:
289:
285:
282:
279:
210:
207:
168:
165:
118:regular tiling
101:
96:
26:
9:
6:
4:
3:
2:
561:
550:
547:
545:
544:Planar graphs
542:
541:
539:
524:
519:
515:
511:
507:
500:
491:
490:
485:
482:
475:
473:
471:
461:
460:
455:
452:
445:
441:
431:
430:Regular graph
428:
426:
423:
421:
418:
416:
413:
412:
406:
404:
401:
397:
396:lattice graph
393:
389:
386:
382:
377:
375:
370:
368:
358:
356:
352:
347:
325:
319:
311:
308:
297:
291:
283:
280:
277:
269:
265:
261:
257:
254:
249:
247:
243:
238:
236:
232:
228:
224:
220:
216:
206:
204:
199:
192:y-coordinates
188:
181:x-coordinates
179:coordinates,
178:
174:
164:
162:
158:
154:
153:lattice graph
149:
147:
143:
139:
133:
131:
127:
123:
119:
99:
83:
79:
75:
71:
67:
63:
59:
58:lattice graph
55:
47:
43:
36:
32:
19:
513:
509:
499:
487:
484:"Grid graph"
457:
444:
415:Lattice path
395:
381:rook's graph
378:
371:
366:
364:
348:
270:grid, where
267:
263:
255:
253:planar graph
250:
241:
239:
231:median graph
226:
222:
212:
197:
186:
172:
170:
152:
150:
145:
141:
137:
134:
65:
61:
57:
54:graph theory
51:
388:chess piece
361:Other kinds
219:path graphs
35:Square grid
538:Categories
436:References
392:chessboard
374:Hanan grid
209:Properties
116:, forms a
66:grid graph
62:mesh graph
18:Grid graph
489:MathWorld
459:MathWorld
235:bipartite
151:The term
409:See also
80:in some
78:embedded
262:of the
246:4-cycle
177:integer
138:lattice
114:
85:
74:drawing
251:Every
72:whose
403:wazir
390:on a
260:minor
258:is a
221:with
144:, or
122:group
70:graph
68:is a
64:, or
48:graph
37:graph
385:rook
379:The
146:grid
142:mesh
56:, a
518:doi
124:of
52:In
540::
514:62
512:.
508:.
486:.
469:^
456:.
372:A
365:A
357:.
346:.
248:.
190:,
163:.
140:,
132:.
76:,
60:,
526:.
520::
492:.
462:.
333:|
329:)
326:H
323:(
320:E
316:|
312:4
309:+
305:|
301:)
298:H
295:(
292:V
288:|
284:2
281:=
278:h
268:h
264:h
256:H
242:n
227:m
223:n
198:m
187:n
100:n
95:R
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
