相交圖型的辨認問題

Abstract

在這篇論文中, 我們將考慮平面上的水平垂直線段所對應的相交圖型的辨 認問題. 我們將找出一個圖型是水平垂直線段的相交圖型的充要條件, 我 們也將列出一些不是此種相交圖型的例子. In this thesis, we shall consider the problem of characterizing the intersection graph of a family of horizontal and vertical segments in the plane which is called a "grid intersection graph". We shall give the necessary and sufficient conditions for a graph to be a grid intersection graph. We shall also list some forbidden graphs of a grid intersection graph.