You can plot it using the `GraphLayout` option:

 Graph[Rule @@@ {{1, 2}, {2, 3}, {3, 1}, {1, 4}, {3, 4}, {2, 4}}, GraphLayout -> "PlanarEmbedding"]

![Mathematica graphics](https://i.sstatic.net/vund3.png).

(BTW: This is the standard Mathematica `Graph`, not the Combinatorica `Graph` function)

Another one:

 truncatedCube =
 {{0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1}, 
 {1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1}, {1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}, 
 {0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0}, {1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0}, 
 {0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
 {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

 AdjacencyGraph[truncatedCube, 
 GraphLayout -> "PlanarEmbedding", 
 VertexLabels -> Thread[Range[Length@truncatedCube] -> Range[Length@truncatedCube]], 
 PlotRangePadding -> 0.5]

![Mathematica graphics](https://i.sstatic.net/UU3lQ.png)