平面グラフは直線だけで描けるか？

頂点を３つもつ完全グラフK3は、正三角形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、その線分は正三角形の辺になります

頂点を４つもつ完全グラフK4は、長方形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、長方形の辺と対角線になります。しかし、対角線は交差してしまうので、どちらか一方を迂回させて(線分でなく)描くことになります。

しかし、正三角形の各頂点とその重心を頂点とすれば、線分の長さは２種類になりますが、K4でも線分で描けます。

頂点を５つもつ完全グラフK5は平面グラフにはなりません。それ以上の完全グラフでも平面グラフにはなりません。

そこで質問です。完全グラフに限らず、どんな平面グラフでも、変形さえすれば、頂点以外で曲がったりカーブしたりすることなく、描くことはできるのでしょうか？

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2005/10/13 12:23

ちょうど手元にあった本を見ただけで, web とかを参考にしたわけではないんですが....

「グラフ G が平面的 ⇔ G には K5 も K3,3 もマイナーとして含まない」
という有名な定理があるんですが, その証明方法 (の 1つ) として
[1] K5 も K3,3 もマイナーとして含まない, 5点以上の 3連結グラフは平面的
[2] K5 も K3,3 もマイナーとして含まない 5点以上のグラフは, 隣接していない 2点をうまく選ぶとその間に辺を加えて得られるグラフにはやっぱり K5 も K3,3 もマイナーとして含まれない
という 2つの命題を組合せる, というのがあるんですが, [1] を証明するときに実際に平面にグラフを描いていて, その描き方をよく見ると「単純グラフならどの辺も直線分で描ける」ことがわかるわけです.
手元で参考にした本は
Bernhard Korte and Jens Vygen, Combinatorial Optimization, Springer
ですが, グラフ理論の本で上の [1] を証明しているのがあれば多分どの本でもよいかと思います.

この回答へのお礼

アドバイスありがとうございます。

お礼日時：2005/10/13 20:26

No.1 回答者： Tacosan 回答日時： 2005/10/12 19:36

ちょいと調べてみましたが, 単純な (つまり自己ループや並行辺を持たない) 平面的グラフは直線分だけで平面上に描くことができます.

この回答へのお礼

回答ありがとうございます。参考ＵＲＬも教えていただければと。

お礼日時：2005/10/13 09:06