グラフの平面性の判定について
スポンサーリンク
概要
- 論文の詳細を見る
An efficient algorithm is presented for determing if a given graph is planar. Algorithm 1 is to test whether or not a given three-connected graph can be embedded in a plane and is based on the planar mesh, which is defined in the three-connected planar graph. If |V(G)| is a number of vertices in the graph G, a time required in the computation by using Algorithm 1 is proportional to |V(G)|. To decide the planarity of a given two-connected graph, further, Algorithm 2 is given in the manner of similar techniques in Algorithm 1.
- 山形大学の論文
- 1976-02-20
著者
関連論文
- インダクタンス行列の実用因子合成
- グラフの等位変換とその応用
- 胞の接触パタ-ンによって分類された反復グラフの木の数の一般式について
- グラフの枝間の距離(電気的距離)とその応用について(グラフ理論とその応用)
- 電気回路計算によるグラフの複雑さの新簡便決定法
- 開閉素子をもつ電気回路網における対称混合方程式の図解法
- 開閉素子をもつ電気回路網の対称混合解析
- カスケ-ド回路網の木積和の計算法
- N色木の計数について
- グラフの平面性の判定について
- 道路網における交通流配分
- 道路交通網のグラフ理論的新解析法
- グラフ理論による通信網の近似解析
- 電気回路の位相幾何的解析における二三の定理
- 過渡現象の時系列による新代数化理論とその二、三の回路への応用
- 伝達アドミツタンスの位相幾何的構成〔英文〕
- 双対ダイアコプティクス〔英文〕
- 回路量の位相性(2)
- 結合parameterを基礎とした回路網解析の一考察
- 知的CIAのためのLispシステムの開発