Tesis ini membahas masalah subgraf planar maksimal yang mengandung subgraf tertentu. Subgraf tertentu yang dimaksud adalah graf terhubung yang derajat setiap verteksnya maksimum dua. Pada tahun 1993, Cai, Han dan Tarjan menyusun sebuah algoritma Maximal Planar Subgraph (algoritma CHT) untuk mencari subgraf planar maksimal dalam sebuah graf G. Algoritma CHT disusun berdasarkan algoritma Planarity Testing yang dikemukakan oleh Hopcroft dan Tarjan pada tahun 1974. Algoritma terakhir ini menggunakan Depth-First-Search (DFS) untuk menyatakan graf sebagai masukan. Graf hasil DFS ini mengandung satu atau lebih spanning tree yang disebut DFS-tree. Algortima CHT tersebut diimplementasikan pada mesin SUNsparc berbasis UNIX(r) System V Release 4.0 di Fasilkom Universitas Indonesia dengan menggunakan bahasa C. Uji coba dilakukan pada graf komplit Kn dengan n verteks dan beberapa graf sembarang. Dari uji coba pada graf komplit Kn dengan n ³ 5 diperoleh kesimpulan bahwa agar memperoleh subgraf planar maksimal dari Kn, jumlah sisi yang harus dihapus minimal adalah 1/2 (n2 - 7n + 12). Pada tesis ini, algoritma CHT dikembangkan untuk menentukan subgraf planar maksimal GP dari sebuah graf G yang mengandung subgraf terhubung GS yang derajat setiap verteksnya maksimum dua. Hal ini dilakukan dengan menjadikan GS sebagai subtree dari salah satu DFS-tree dari G.