We investigate three problems: obstacle representation of graphs, computing the bundled crossing number of a graph, and universal covers for families of triangles.
First, we study single-obstacle graphs: visibility graphs that can be represented by placing vertices as points in the plane and a simple polygonal obstacle (vertices are adjacent if and only if they can see each other). An obstacle is called an outside-obstacle if it lies in the unbounded component of the visibility drawing and an inside-obstacle otherwise. We establish several subclasses of single-obstacle graphs and find a smallest graph that is not a single-obstacle graph. We show that inside-obstacle graphs and outside-obstacle graphs are incomparable. We prove that the single-obstacle graph sandwich recognition problem and the simple-polygon visibility graph sandwich recognition problem are NP-hard.
Second, we study a technique to reduce the visual complexity of a graph drawing by bundling locally parallel edges, where we count the number of bundled crossings and call its minimum over all simple drawings the bundled crossing number. We show that computing the bundled crossing number is NP-complete. We also show that computing several variants of the circular bundled crossing number where vertices are placed on a circle and edges are drawn inside the circle are fixed-parameter tractable.
Third, given a family of triangles, we want to find a convex cover of the smallest area that can accommodate a congruent copy of every triangle. We conjecture that the answer is a triangle for any set of triangles, and show that this conjecture is equivalent to the conjecture that the answer is a triangle for the family of triangles contained in any given convex set. We demonstrate that the answer is indeed a triangle for two cases, namely (i) triangles of unit circumradius and (ii) any two triangles.
단일 장애물 그래프란 단순 다각형인 장애물 하나를 사용하여 정점을 평면 위에 점으로 나타내었을 때 가시성 그래프로 표현될 수 있는 그래프이다. 단일 장애물 그래프가 아닌 가장 작은 그래프를 결정한다. 외부 장애물 그래프와 내부 장애물 그래프가 비교 불가능한 그래프 클래스임을 보인다. 단일 장애물 그래프와 단순 다각형 가시성 그래프의 샌드위치 인식 문제가 비결정론적 다항시간 난해임을 보인다.
그래프 다발 교차수란 국소적으로 평행한 간선들을 다발로 만들어 다발 교차의 수가 최소화되는 그래프 그림에서의 다발 교차수를 말한다. 다발 교차수를 계산하는 것은 비결정론적 다항시간 완전임을 보이고, 원형 다발 교차수와 그 이형들이 고정-인자 트랙터블임을 보인다.
삼각형의 집합이 주어졌을 때 각 삼각형의 합동형을 덮을 수 있는 가장 작은 넓이의 볼록 덮개를 찾고자 한다. 어떠한 삼각형의 집합이 주어지더라도 가장 작은 볼록 덮개는 삼각형이라고 추측하며, 임의의 두 개의 삼각형으로 이루어진 집합이나 단위 원에 들어가는 삼각형의 집합에 대해서 참임을 보인다.
