STUDY 1: Chessboard Problems with Obstructions

Represent each square on a chessboard of arbitrary size by a point ( vertex ) and then, for every pair of squares, connect their points with an edge if a chess queen could move from one square to the other in a single move. These vertices and edges constitute the queens graph for that chessboard. In two separate but related mathematics projects, we study what happens to the queens graph and related graphs if the board has one or more obstacles ( pawns ) placed to restrict the movement of the queens. Project 1: (Hufford & Blankenship, Book Embeddings of Chessboard Graphs) To embed a graph in a book, linearly order the vertices in the spine (line) and place the edges in pages (half-planes) so that no two edges cross in a page. Book thickness is the minimum number of pages needed over all possible vertex and edge assignments. Upper and lower bounds on book thickness are provided for the n x n queens graph and for the subgraph of the n x n queens graph resulting from a single pawn placed anywhere on the n x n board